Electronic messages are normally transmitted between remote correspondents via a communications system typically including a network of interconnected computers. Such messages are readily intercepted and viewed by others using the network. Thus, correspondents desiring privacy may encrypt or encode a message in a way that only the recipient can decrypt or decode it to view the message contents. A common encryption technique is disclosed in U.S. Pat. No. 4,405,829 to Rivest et al., which is incorporated by reference. The technique is also known as the RSA technique.
Rivest discloses a "public key" technique in which each user desiring to receive encrypted messages creates a numerical encoding key that may be mathematically applied by a sender to an original message to encode the message. The recipient also creates and maintains secretly a decoding key that, when mathematically applied to the encoded message, decodes it to regenerate the original message. Each encoding key includes the product of two large prime numbers. These two prime factors can not be determined from their product without extraordinary computation efforts. The secret decoding key is also derived from the same two secret prime numbers. Each recipient posts his or her own encoding key in a public repository so that all correspondents wishing to send confidential messages to that recipient may use that recipient's key to encode messages. The public key repository is like a telephone directory, in that it enables anyone to look up a listed individual and obtain a number required for communication. Because of the difficulty of factoring the prime factors in a public encoding key, the decoding key remains secure to a degree.
The difficulty of deriving the secret decoding key from a public encoding key varies with the size of the key. With modest computing power, a small product of two primes may be factored by attempting to divide it by each successive prime number until division occurs without a remainder. Larger numbers require more sophisticated techniques, and as a general rule, factorization is more difficult with larger numbers. Using current technology, a public key expressed as a string of 512 binary "one" or "zero" bits will require several thousand hours of computer time to crack by factoring, and may be considered "difficult," but not "bulletproof." A key of 1024 bits is currently considered "bulletproof" or impossible to crack; with the best available factorization techniques, it would require all global computing resources to be devoted to the task for many years. Even as computer calculation speed increases impressively, a small increase of the key size can preserve essentially absolute security of the private decoding key.
While perfect privacy may be desired by individual correspondents, there is occasionally a need for a legitimate monitoring authority to decode a message. Such authorities may include law enforcement agencies seeking evidence of criminal activity, employers seeking to investigate dissemination of trade secrets, and governments seeking to prevent espionage by the dissemination of national security secrets, including secret communications by terrorists into and out of the country. Thus, governments may limit the size of keys to ensure that decoding messages is merely difficult, but not impossible. Unfortunately, this means that users are vulnerable to decoding of their public keys and messages by the extraordinary efforts of unauthorized interceptors or "eavesdroppers". This is of particular concern as major financial transactions and sensitive technology may need to be transmitted electronically. Thus, there is a trade-off between privacy to protect efficient commerce, and decodability to ensure national security.
In current practice, there is no limit placed on the size of public keys used in domestic communications, but keys used for international communications are limited. U.S. law is believed currently to prohibit international transmission or receipt of a communication encoded with a public key greater than 512 bits in length. As a result, a commercially sensitive communication within a multinational company, but which crosses national borders, may be vulnerable to interception and decoding, or must be restricted to less efficient means of communication. If some communications are exempted from the key length limit, such as for international banking, an opportunity exists for international espionage or terrorist communications undetectable by government investigators.
Accordingly, there is a need for an encryption system that permits correspondents to maintain an higher level of security against unauthorized interceptors, and a lesser level of security against a monitoring authority. This need is provided by a method of encoded communication in which a receiver generates a receiver public key by looking up a monitoring authority public key, multiplying four prime numbers, and encoding the identities of two of the prime numbers with the monitoring authority public key. The receiver makes his or her public key available to a sender, who creates a message, encodes it with the receiver public key, and transmits it to the receiver. The receiver then decodes the encoded message with the four prime numbers. The monitoring authority may decode the two prime numbers of the receiver's key, and factorize the product of the remaining primes. An unauthorized party would be faced with the much more difficult or impossible task of factorizing the original product of the four primes.